package org.bear.linkList;

/*
    148.排序链表

    给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表
    0 1
 */
public class SortList {

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        if (head.next.next == null) {
            if (head.val > head.next.val) {
                head.next.next = head;
                ListNode t = head.next;
                head.next = null;
                return t;
            }else {
                return head;
            }
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode temp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(temp);
        return mergeSortedList(left, right);
    }

    private ListNode mergeSortedList(ListNode a, ListNode b) {
        if(a == null &&  b == null){
            return null;
        }else if(a == null){
            return b;
        }else if(b == null){
            return a;
        }else{
            ListNode head = new ListNode(0);
            ListNode p = head;
            while(a!=null && b!=null){
                if(a.val<b.val){
                    p.next = a;
                    a = a.next;
                }else {
                    p.next = b;
                    b = b.next;
                }
                p = p.next;
            }
            if (a!=null){
                p.next = a;
            }
            if (b!=null){
                p.next = b;
            }
            return head.next;
        }
    }

    public static void main(String[] args) {
        SortList s = new SortList();
        s.sortList(ListNode.generate(new int[]{3,2,5,4,1}));
    }

}
